package com.demo.java.OD351_400.OD357;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【找单词(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146165318
 */
public class OdMain {
    // 使用Scanner来读取输入，并且指定分隔符为逗号和换行符
    private static final Scanner in = new Scanner(System.in).useDelimiter("[,\\n]");

    public static void main(String[] args) {
        // 读取矩阵的大小n
        int n = in.nextInt();
        // 初始化一个n x n的矩阵，用来存储输入的字符串
        String[][] matrix = new String[n][n];

        // 读取n x n矩阵的元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = in.next();
            }
        }

        // 读取目标字符串
        String target = in.next();

        // 遍历矩阵中的每一个位置，尝试寻找目标字符串
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 用一个链表来存储路径
                LinkedList<Integer[]> path = new LinkedList<>();
                // 调用深度优先搜索算法来查找目标字符串
                if (dfs(i, j, 0, path, n, matrix, target)) {
                    // 如果找到了目标字符串，打印路径并返回
                    printPath(path);
                    return;
                }
            }
        }

        // 如果没有找到目标字符串，打印"N"
        System.out.println("N");
    }

    // 深度优先搜索 (DFS) 用于查找目标字符串
    private static boolean dfs(int i, int j, int k, LinkedList<Integer[]> path,
                               int n, String[][] matrix, String target) {
        // 如果越界或者当前字符不等于目标字符串的第k个字符，返回false
        if (i < 0 || i >= n || j < 0 || j >= n ||
                !target.substring(k, k + 1).equals(matrix[i][j])) {
            return false;
        }

        // 将当前的位置加入路径
        path.add(new Integer[]{i, j});

        // 如果已经找到了目标字符串的所有字符，返回true
        if (path.size() == target.length()) {
            return true;
        }

        // 记录当前字符，并将当前矩阵中的字符设为null，避免重复访问
        String tmp = matrix[i][j];
        matrix[i][j] = null;

        // 尝试四个方向进行深度优先搜索（上下左右）
        boolean res = dfs(i - 1, j, k + 1, path, n, matrix, target) // 向上
                || dfs(i + 1, j, k + 1, path, n, matrix, target) // 向下
                || dfs(i, j - 1, k + 1, path, n, matrix, target) // 向左
                || dfs(i, j + 1, k + 1, path, n, matrix, target); // 向右

        // 如果四个方向都没有找到，恢复原来的字符并从路径中删除当前位置
        if (!res) {
            matrix[i][j] = tmp;
            path.removeLast();
        }

        return res;
    }

    // 打印路径，将路径中的每一个坐标以“行,列”的形式输出
    private static void printPath(LinkedList<Integer[]> path) {
        StringBuilder result = new StringBuilder();
        for (Integer[] pos : path) {
            result.append(pos[0]).append(",").append(pos[1]).append(",");
        }
        // 输出路径，去掉最后一个多余的逗号
        System.out.println(result.substring(0, result.length() - 1));
    }
}